package cn.aylog.recursion;

import java.util.Stack;

/**
 * 练习
 *  八皇后问题
 */
public class Demo2 {
    public static void main(String[] args) {
        Queen queen = new Queen();
        for(int i=0; i<8; i++) {
            queen.play(0,i);
        }
        System.out.println(queen.judgeCount);
//        queen.showMaze();

    }
}

class Queen {
    private int maze[][]; // 迷宫
    private static final int NONE = 0; // 无人
    private static final int PERSON = 2; // 有人
    private static final int DEAD = 3; // 冲突
    private int cnt = 1;
    public int judgeCount = 0;

    public Queen() {
        maze = new int[8][8];
    }

    /**
     * 输出地图
     */
    public void showMaze() {
        int row = maze.length;
        int col = maze[0].length;
        for(int x=0; x<row; x++) {
            for(int y=0; y<col; y++) {
                System.out.print(maze[x][y] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 放置人
     */
    public void setPerson(int x, int y) {
        maze[x][y] = PERSON;
    }

    private void step(int x, int y, boolean flag) {
        if(flag) {
            System.out.printf("(%d,%d) = %d", x, y, maze[x][y]);
        }
    }

    /**
     * 检测皇后是否冲突
     */
    public boolean isConflict(int x, int y) {
        boolean flag = false;
        boolean showStep = false;
        if(showStep) {
            System.out.printf("当前点: (%d, %d) = %d, 冲突点: ", x, y, maze[x][y]);
        }
        judgeCount++;
        for(int i = 0; i<8; i++) {
            if(i != x && maze[i][y] == PERSON) {
                step(i,y,showStep);
                flag = true;
                break;
            } else if(i != y && maze[x][i] == PERSON) {
                step(x, i,showStep);
                flag = true;
                break;
            } else if(i != 0 &&  x-i >= 0 && y-i >= 0 && maze[x-i][y-i] == PERSON) {
                step( x-i, y-i,showStep);
                flag = true;
                break;
            } else if(i != 0 && y+i < 8 && x-i >= 0 && maze[x-i][y+i] == PERSON) {
                step(x-i, y+i,showStep);
                flag = true;
                break;
            }
        }
        if (showStep) {
            System.out.println();
        }
        return flag;
    }

    private boolean isEnd() {
        for(int i =0; i<8; i++) {
            if(maze[7][i] == PERSON) {
                return true;
            }
        }
        return false;
    }

    /**
     * 解答
     */
    public boolean play(int x, int y) {
        if(isEnd()) {
            return true;
        } else {
            if(maze[x][y] == NONE) {
                setPerson(x, y);
                for(int i=0; i<8; i++) {
                    if(x+1 < 8 && !isConflict(x+1, i) && play(x+1, i)) {
                        return true;
                    }
                }
                if(isEnd()) {
                    System.out.printf("第%d种:\n", cnt++);
                    showMaze();
                };
                // 重置
                maze[x][y] = NONE;
                return false;
            } else {
                return false;
            }
        }
    }

}
